#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//void dfs(int row, int col)
//{
//    for (int i = 0;i < 9;i++)
//    {
//        if (isdigit(board[row][i]))
//        {
//            int num = board[row][i] - '0';
//            row[row][num] = col[i][num] = grid[row / 3][i / 3][num] = true;
//        }
//        else
//        {
//            for (int j = 1;j <= 9;j++)
//            {
//                if (row[row][j] || col[i][j] || grid[row / 3][i / 3][j]) continue;
//                board[row][i] = '0' + j;
//            }
//            if (j == 10) return;
//        }
////    }
////}
//
//class Solution789
//{
//public:
//    int row[9][10]={0}, col[9][10]={0}, grid[3][3][10]={0};
//    vector<vector<char>>& board;
//    vector<vector<char>> tmp;
//    Solution(vector<vector<char>>& _board)
//        :board(_board)
//    {
//    }
//    void solveSudoku(vector<vector<char>>& _board)
//    {
//        board = _board;
//        for (int r=0;r<9;r++)
//        {
//            for(int c=0;c<9;c++)
//            if (isdigit(board[r][c]))
//            {
//                int num = board[r][c] - '0';
//                row[r][num] = col[c][num] = grid[r / 3][c / 3][num] = true;
//            }
//        }
//        dfs_row(0);
//
//    }
//    void dfs_row(int r)
//    {
//        if (r == 9) return;
//        dfs_col(r, 0);
//    }
//    void dfs_col(int r, int c)
//    {
//        if (r == 8 && c == 9)
//        {
//            tmp = board;
//        }
//        if (c == 9)
//        {
//            dfs_row(r + 1);
//        }
//        if (isdigit(board[r][c]))
//        {
//            dfs_col(r, c + 1);
//        }
//        else
//        {
//            int i = 1;
//            for (;i <= 9;i++)
//            {
//             
//                if (row[r][i] || col[c][i] || grid[r / 3][c / 3][i]) continue;
//                row[r][i] = col[c][i] = grid[r / 3][c / 3][i] = true;
//                board[r][c] = '0' + i;
//                dfs_col(r, c + 1);
//                row[r][i] = col[c][i] = grid[r / 3][c / 3][i] = false;
//                board[r][c] = '.';
//
////            }
////        }
////    }
////};
//class Solution {
//public:
//    int row[9][10] = { 0 }, col[9][10] = { 0 }, grid[3][3][10] = { 0 };
//    void solveSudoku(vector<vector<char>>& board) 
//    {
//
//    }
//    bool dfs(vector<vector<char>>& board)
//    {
//        for (int i = 0;i < 9;i++)
//        {
//            for (int j = 0;j < 9;j++)
//            {
//                if (isdigit(board[i][j]))
//                {
//                    int num = board[i][j] - '0';
//                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
//                }
//            }
//        }
//        for (int i = 0;i < 9;i++)
//        {
//            for (int j = 0;j < 9;j++)
//            {
//                if (isdigit(e))continue;
//                for (int k = 1;k <= 9;k++)
//                {
//                    if (row[i][k] || col[j][k] || grid[i / 3][j / 3][k]) continue;
//                }
//            }
//
//        }
//    }
//};

class Solution45
{
public:
    bool check[16][16];
    int Max = 0, m, n;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int getMaximumGold(vector<vector<int>>& grid)
    {
        m = grid.size(), n = grid[0].size();
        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                if (grid[i][j] != 0)
                {

                    check[i][j] = true;
                    dfs(grid, i, j, 0);
                    check[i][j] = false;
                }
            }
        }
        return Max;
    }
    void dfs(vector<vector<int>>& grid, int x, int y, int cur)
    {
        cur += grid[x][y];
        for (int i = 0;i < 4;i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (ny >= 0 && ny < n && nx < m && nx >= 0 && check[x + dx[i]][y + dy[i]] == false && grid[nx][ny] != 0)
            {
                check[x + dx[i]][y + dy[i]] = true;
                dfs(grid, x + dx[i], y + dy[i], cur);
                check[x + dx[i]][y + dy[i]] = false;
            }
        }
        Max = max(cur, Max);
        return;

    }
};

class Solution4
{
public:
    int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
    int m, n;
    vector<vector<int>> ret;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)
    {
        m = heights.size(), n = heights[0].size();
        vector<vector<bool>> check1(m, vector<bool>(n, false));
        vector<vector<bool>> check2(m, vector<bool>(n, false));
        for (int i = 0;i < n;i++)
        {
            dfs(0, i, heights, check1);
            dfs(m - 1, i, heights, check2);
        }
        for (int i = 0;i < m;i++)
        {
            dfs(i, 0, heights, check1);
            dfs(i, n - 1, heights, check2);
        }
        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                if (check1[i][j] == true && check2[i][j] == true)
                    ret.push_back({ m,n });
            }
        }

        return ret;

    }
    void dfs(int x, int y, vector<vector<int>>& heights, vector<vector<bool>>& check)
    {
        check[x][y] = true;
        for (int i = 0;i < 4;i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && check[nx][ny] == false && heights[nx][ny] >= heights[x][y])
            {
                dfs(nx, ny, heights, check);
            }
        }
    }
};


//class Solutionll
//{
//public:
//    int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 }, m, n, oldColor;
//    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
//    {
//        m = image.size(), n = image[0].size(), oldColor = image[sr][sc];
//        dfs(image, sr, sc, color);
//        return image;
//    }
//    void dfs(vector<vector<int>>& image, int sr, int sc, int color)
//    {
//        image[sr][sc] = color;
//        for (int i = 0;i < 4;i++)
//        {
//            int nx = sr + dx[i], ny = sc + dy[i];
//            if (nx >= 0 && nx < m && ny >= 0 && ny < n && image[nx][ny] == oldColor)
//            {
//                dfs(image, nx, ny, color);
//            }
//        }
//        return;
//    }
//};
class Solution
{
public:
    int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 }, m, n, oldColor;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        m = image.size(), n = image[0].size(), oldColor = image[sr][sc];
        dfs(image, sr, sc, color);

        return image;
    }
    void dfs(vector<vector<int>>& image, int sr, int sc, int color)
    {
        image[sr][sc] = color;
        for (int i = 0;i < 4;i++)
        {
            int nx = sr + dx[i], ny = sc + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && image[nx][ny] == oldColor)
            {
                dfs(image, nx, ny, color);
            }
        }
    }
};
int main()
{
    vector<vector<int>> v = { {1,1,1},{1,1,0},{1,0,1} };
    Solution().floodFill(v, 1, 1, 2);
	return 0;
}